package main

import (
	"fmt"
	"sort"
)

//#link: https://leetcode-cn.com/problems/valid-triangle-number/
func main() {
	nums := []int{2, 2, 3, 4}
	fmt.Println(triangleNumber(nums))
}

//任意两边之和大于第三边，任意两边之差小于第三边
func triangleNumber(nums []int) int {
	if len(nums) <= 3 {
		return 0
	}
	//先排序
	sort.Ints(nums)
	//从前两个边开始进行窗口滑动
	first, second := 0, 1
	result := 0
	for first < len(nums)-1 {
		sum := nums[first] + nums[second]
		sub := nums[second] - nums[first]
		//寻找在sub-sum范围间的数字
		for i := second + 1; i < len(nums); i++ {
			if nums[i] > sub && nums[i] < sum {
				result++
			}
		}
		first++
		second++
	}
	return result

}
